Programmable integrated circuit (IC) devices are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of programmable IC, the field programmable gate array (FPGA), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (IOBs), configurable logic blocks (CLBs), dedicated random access memory blocks (BRAM), multipliers, digital signal processing blocks (DSPs), processors, clock managers, delay lock loops (DLLs), and so forth.
Each programmable tile typically includes both programmable interconnect and programmable logic. The programmable interconnect typically includes a large number of interconnect lines of varying lengths interconnected by programmable interconnect points (PIPs). The programmable logic implements the logic of a user design using programmable elements that can include, for example, function generators, registers, arithmetic logic, and so forth.
The programmable interconnect and programmable logic are typically programmed by loading a stream of configuration data into internal configuration memory cells that define how the programmable elements are configured. The configuration data can be read from memory (e.g., from an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
Another type of programmable IC is the complex programmable logic device, or CPLD. A CPLD includes two or more “function blocks” connected together and to input/output (I/O) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in programmable logic arrays (PLAs) and programmable array logic (PAL) devices. In CPLDs, configuration data is typically stored on-chip in non-volatile memory. In some CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration (programming) sequence.
For all of these programmable ICs, the functionality of the device is controlled by data bits provided to the device for that purpose. The data bits can be stored in volatile memory (e.g., static memory cells, as in FPGAs and some CPLDs), in non-volatile memory (e.g., FLASH memory, as in some CPLDs), or in any other type of memory cell.
Other programmable ICs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These programmable IC are known as mask programmable devices. Programmable ICs can also be implemented in other ways, e.g., using fuse or antifuse technology. The phrase “programmable IC” can include, but is not limited to these devices and further can encompass devices that are only partially programmable. For example, one type of programmable IC includes a combination of hard-coded transistor logic and a programmable switch fabric that programmably interconnects the hard-coded transistor logic.
A circuit design to be implemented within an IC must be routed. In general, the term “routing” refers to the process of establishing connectivity between elements, e.g., pins, of the circuit design. Elements are coupled using routing resources, e.g., wires. Within a programmable IC, the programmable interconnect structure already exists within the device. Thus, with respect to a programmable IC, routing refers to the process of assigning signals, also known as “nets” or networks, of the circuit design to particular routing resources. The programmable IC is programmed to establish connections between appropriate ones of the routing resources to implement the specified routes, thereby establishing the necessary physical connections among the different circuit elements of the circuit design within the programmable IC.
When too many nets of a circuit design compete for the same set of routing resources, given that the routing resources of a programmable IC are fixed and finite, the circuit design is said to suffer from routing congestion. Routing congestion is a function of several different factors including the circuit design itself, the placement of components of the circuit design to particular locations on the programmable IC, routing delays, and the architecture of the programmable IC within which the circuit design is to be implemented.
A “router” refers to a circuit design tool that assigns signals of the circuit design to routing resources. The router determines routes for nets of the circuit design so that no more than one signal is assigned to each routing resource of the programmable IC. The condition where two or more signals are assigned to the same routing resource of a programmable IC is referred to as “overlap” or an “overlap condition.” An overlap is effectively a short circuit between the two signals of the circuit design assigned to the same routing resource. A router not only seeks to eliminate or avoid overlaps, but typically attempts to optimize the routes that are determined according to one or more other metrics.